package 图;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @description: 根据No743来熟悉三种最短路径图算法
 * @author: 小白白
 * @create: 2021-12-19
 **/

public class Base图论算法 {

    /**
     * 构建图的两种数据结构
     * 1. 通用 [n][n] 容易理解但空间占用大
     * 2. 邻接表 四个数组
     *    A(边,某个节点边集合的首发)
     *    B(边,当前边的下一条边)
     *    C(节点,某条边对应的节点)
     *    D(权重,当前边的权重)
     */

    /**
     * 三个算法
     * 1. 弗洛伊德算法 负权回路不可用(一个环的权值和为负数,称负权回路) O(n^3)
     * 2. 迪杰斯特拉算法 [负权边不可用] O(n^2)
     * 3. 贝尔曼-福特算法 负权回路不可用  O(节点数量*边数量)
     */

    // 弗洛伊德算法
    public int networkDelayTimeFloyd(int[][] times, int n, int k) {

        /**
         * 单单一个二维数据存储点到点之间的距离即可
         * 中转节点 - 起点 - 终点 [三层循环]
         */
        int INF = 0x3f3f3f3f;
        // i -> j 的距离
        int[][] dp = new int[101][101];

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    dp[i][j] = 0;
                    dp[j][i] = 0;
                } else {
                    dp[i][j] = INF;
                    dp[j][i] = INF;
                }
            }
        }

        // 存图
        for (int[] time : times) {
            int a = time[0];
            int b = time[1];
            int c = time[2];
            // 单向
            dp[a][b] = c;
        }

        // 弗洛伊德算法
        for (int m = 1; m <= n; m++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][m] + dp[m][j]);
                }
            }
        }

        int max = Integer.MIN_VALUE;

        for (int i = 1; i <= n; i++) {
            max = Math.max(max, dp[k][i]);
        }

        return max == INF ? -1 : max;
    }

    // 狄克斯特拉算法
    public int networkDelayTimeDijkstra(int[][] times, int n, int k) {

        /**
         * 距离数据 + 二维数组 + 是否已经最短数组
         * 0. 堆放入
         * 1. 每次将离k节点最近的节点x取出,(那么此时节点已经最短,标志一下)
         * 2. 根据x节点更新其他节点到k节点的距离,更新后将其他节点放入堆中
         * 3. 一直遍历,直到堆为空
         */

        // 无穷大
        int INF = 0x3f3f3f3f;
        // k 到每个节点的最短距离
        int[] dist = new int[n + 1];
        // 各个节点之间的关系
        int[][] dp = new int[n + 1][n + 1];
        // 到某个节点是否为最短距离
        boolean[] ok = new boolean[n + 1];

        // base1 k到每个点的距离无限(self为0)
        Arrays.fill(dist, INF);
        dist[k] = 0;
        // base2 每个点之间的距离也都是无限大(self为0)
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    dp[i][j] = 0;
                    dp[j][i] = 0;
                } else {
                    dp[i][j] = INF;
                    dp[j][i] = INF;
                }
            }
        }

        for (int[] time : times) {
            int a = time[0];
            int b = time[1];
            int c = time[2];
            dp[a][b] = c;
            // k节点到b节点的距离为c
            if (a == k) {
                dist[b] = c;
            }
        }

        // 开始dijkstra算法
        // 放入节点构建小堆,只放入k能直接到达的点
        /**
         * 堆顶元素离k最近
         */
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(i -> dist[i]));
        for (int i = 1; i < dist.length; i++) {
            if (dist[i] != INF) {
                // 仅放入能到达的
                priorityQueue.add(i);
            }
        }
        // 1.从dist中找到距离k最近的点x,然后由x节点中转,看能缩短到哪个点的距离
        while (!priorityQueue.isEmpty()) {

            // 吐出距离最短的节点
            Integer index = priorityQueue.poll();

            if (ok[index]) {
                continue;
            }

            // 最先吐出遍历,必定是最优的
            ok[index] = true;

            // 从index节点出发能触及点的距离
            int[] arr = dp[index];

            for (int i = 1; i < arr.length; i++) {
                // i为节点 value为距离
                int allLength = dp[k][index] + arr[i];
                if (allLength < dp[k][i]) {
                    // 更新k到i的距离,并且标记i已是最优解
                    dp[k][i] = allLength;
                    dist[i] = allLength;
                    // 放入新触及的节点
                    priorityQueue.add(i);
                }
            }

        }

        int minValue = Integer.MIN_VALUE;
        // 完毕,遍历dist
        for (int i = 1; i < dist.length; i++) {
            int w = dist[i];
            minValue = Math.max(minValue, w);
        }

        return minValue == INF ? -1 : minValue;
    }

    private class AdjacencyTable {

        int index;
        // 节点的第一个边
        int[] item_edge;
        // 边的下一个边
        int[] next_edge;
        // 边的指向
        int[] edge_end;
        // 边权重
        int[] edge_weight;

        // n个节点 m条边
        public AdjacencyTable(int n, int m) {
            this.item_edge = new int[n];
            this.next_edge = new int[m];
            this.edge_end = new int[m];
            this.edge_weight = new int[m];
            /**
             * 节点的第一个边初始化为-1,因为这是尾巴
             */
            Arrays.fill(this.item_edge, -1);
        }

        // a指向b,权重为c
        public void add(int a, int b, int c) {
            // a的首个边
            int lastEdge = this.item_edge[a];
            // 当前边的下一个边就是a的原首个边
            this.next_edge[this.index] = lastEdge;
            // 更新a的首个边
            this.item_edge[a] = this.index;
            // 当前边的指向
            this.edge_end[this.index] = b;
            // 更新当前边的权重
            this.edge_weight[this.index] = c;
            this.index++;
        }

    }

    public int networkDelayTimeBellmanFord(int[][] times, int n, int k) {

        // 邻接表: index边 节点对应边集合首元素 边的下一个边 某个边的终点 边权重

        int INF = 0x3f3f3f;
        int[] dist = new int[n + 1];
        Arrays.fill(dist, INF);
        dist[k] = 0;
        /**
         * 使用高级的邻接表 (也可以使用低级的类)
         */
        AdjacencyTable adjacencyTable = new AdjacencyTable(110, 6010);
        for (int[] time : times) {
            int a = time[0];
            int b = time[1];
            int c = time[2];
            adjacencyTable.add(a, b, c);
            if (a == k) {
                dist[b] = c;
            }
        }

        // 直接迭代n次, 每次都松弛n次(节点数)
        for (int count = 1; count <= n; count++) {
            int[] prev = dist.clone();
            for (int node = 1; node <= n; node++) {
                // 开始遍历所有的节点, k到x的距离 = min(原, item到x + prev[item])

                // 邻接表: 节点首边 下条边 是否没边了
                // 首边
                int edge = adjacencyTable.item_edge[node];

                for (; edge != -1; edge = adjacencyTable.next_edge[edge]) {
                    // 当前边的终点
                    int end = adjacencyTable.edge_end[edge];
                    // 当前边的权重
                    int weight = adjacencyTable.edge_weight[edge];
                    // 更新到终点的距离 min(原, 中转点node + 下边权重)
                    dist[end] = Math.min(dist[end], prev[node] + weight);
                }
            }
        }

        int result = 0;
        for (int i = 1; i < dist.length; i++) {
            result = Math.max(result, dist[i]);
        }

        return result == INF ? -1 : result;
    }

    public static void main(String[] args) {
        Base图论算法 n = new Base图论算法();
        int[][] arr = new int[][]{{2, 1, 1}, {2, 3, 1}, {3, 4, 1}};
        int result = n.networkDelayTimeFloyd(arr, 4, 2);
        System.out.println(result);
        int result2 = n.networkDelayTimeDijkstra(arr, 4, 2);
        System.out.println(result2);
        int result3 = n.networkDelayTimeBellmanFord(arr, 4, 2);
        System.out.println(result3);
    }

}
